package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/30 12:06
 * @description：https://leetcode-cn.com/problems/hand-of-straights/
 */
public class 一手顺子 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.isNStraightHand(new int[]{1, 1, 2, 2, 3, 3}, 2));
    }

    /*
    class Solution {
        // 使用哈希
        public boolean isNStraightHand(int[] hand, int groupSize) {
            int n = hand.length;
            if (n % groupSize != 0) return false;
            Arrays.sort(hand);
            Map<Integer, Integer> map = new HashMap<>();
            for (int i : hand) {
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
            for (int cur : hand) {
                if (map.get(cur) == 0) continue;
                for (int j = cur; j < cur + groupSize; j++) {
                    if (!map.containsKey(j) || map.get(j) == 0) {
                        return false;
                    } else {
                        map.put(j, map.get(j) - 1);
                    }
                }
            }
            return true;
        }
    }
     */
    class Solution {
        public boolean isNStraightHand(int[] hand, int m) {
            Map<Integer, Integer> map = new HashMap<>();
            // 小顶堆
            PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a));
            for (int cur : hand) {
                map.put(cur, map.getOrDefault(cur, 0) + 1);
                queue.offer(cur);
            }
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                if (map.get(cur) == 0) continue;
                for (int i = 0; i < m; i++) {
                    int cnt = map.getOrDefault(cur + i, 0);
                    if (cnt == 0) return false;
                    map.put(cur + i, cnt - 1);
                }
            }
            return true;
        }
    }
}
